The present application relates generally to an improved data processing apparatus and method and more specifically to mechanisms for improving the performance of firewall packet filtering.
Packet classification is a function performed by modern Internet routers whose aim it is to classify packets into “classes” or “flows” according to an established rule set that looks at multiple fields of each packet. Once this classification is performed, different actions can be performed on the data packets depending on the results of the classification. One example of an algorithm that may be implemented by routers to perform such classification is the G-filter algorithm.
The “G-filter” algorithm is a packet filtering algorithm that supports fast matching of packet 5-tuples to a listing of firewall rules n-tuples (where n is less than or equal to 5). In the G-filter algorithm, each packet header has two addresses, two ports, and a transport protocol. Each firewall rule specifies ranges of values for one or more of these 5 fields. Thus, in the 5-tuple version of G-filter, each rule falls into one of 32 classes, depending on which tuple fields the rule matches. G-filter calls these classes “fallback sets.”
For example, if two rules both regulate packets only by the packets' destination addresses and destination ports, the G-filter indicates that these two rules are in the same fallback set. If another rule regulates packets by destination address, destination port, and transport protocol, then G-filter indicates that this rule is in a different fallback set. It is convenient to label each fallback set of rules with a 5-bit string, in which each 1 bit identifies a tuple-dimension that all of the set's rules are associated with or care about:                0th bit: rules that match packets by source-address.        1st bit: rules that match packets by destination-address.        2nd bit: rules that match packets by source-port.        3rd bit: rules that match packets by destination-port.        4th bit: rules that match packets by transport-protocol.        
G-filter builds a separate search-tree for each fallback set in a rule set. At packet matching time, G-filter searches every fallback set's search tree. More information about the G-filter algorithm may be found in Geraci et al., “Packet Classification via Improved Space Decomposition Techniques,” IEEE 2005.